/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 5/28/2008
 */

#ifndef BTNODE_H
#define BTNODE_H

#include "RecordFile.h"
#include "PageFile.h"
#include <stdio.h>
#include <string.h>
#include <cstdlib>

class BTNode
{
  public:

    static const int LEAF_START_POS = 0;

    /**
      * Return true if the node is a leaf node,
      * Return false if the node is a non leaf node.
      */
    bool isLeaf();

    /**
      * Return true if the node is full,
      * otherwise, return false.
      */
    virtual bool isFull() = 0;

    /**
     * Return the number of keys stored in the node.
     * @return the number of keys in the node
     */
     int getKeyCount();

    /**
     * Set the key count in the node to keyCount
     * @param keyCount[IN] the key count value for the node
     * @return 0 if successful. Return an error code if there is an error.
     */
     RC setKeyCount( int keyCount );

    /**
     * Read the content of the node from the page pid in the PageFile pf.
     * @param pid[IN] the PageId to read
     * @param pf[IN] PageFile to read from
     * @return 0 if successful. Return an error code if there is an error.
     */
     RC read(PageId pid, const PageFile& pf);

    /**
     * Write the content of the node to the page pid in the PageFile pf.
     * @param pid[IN] the PageId to write to
     * @param pf[IN] PageFile to write to
     * @return 0 if successful. Return an error code if there is an error.
     */
     RC write(PageId pid, PageFile& pf);


  protected:
    /**
     * The main memory buffer for loading the content of the disk page
     * that contains the node.
     */
     char buffer[PageFile::PAGE_SIZE];
    /**
      * the starting position to store the key count of a node
      */
     static const int KEYCOUNT_START_POS = sizeof(int);
};

/**
 * BTLeafNode: The class representing a B+tree leaf node.
 */
class BTLeafNode : public BTNode {
  public:

   /**
     * Constructor for BTLeafNode.
     * Set the leaf field to be 0, indicating this is a leaf node;
     * Set the number of keys to be zero.
     */
    BTLeafNode();

   /**
     * Initialize the leaf node,
     * such that the leaf field is set to be 0,
     * indicating this is a leaf node;
     * Set the number of keys to be zero.
     */
    void initialize();

   /**
     * Return true if the node is full,
     * otherwise, return false.
     */
    bool isFull();

   /**
    * Insert the (key, rid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param rid[IN] the RecordId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, const RecordId& rid);

   /**
    * Insert the (key, rid) pair to the node
    * and split the node half and half with sibling.
    * After the split, the sibling node's next node pageid field is set to be
    * the next node's pageid value in the current node,
    * and the current node's next node pageid area is set to be the sibling's pageid.
    * The first key of the sibling node is returned in siblingKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert.
    * @param rid[IN] the RecordId to insert.
    * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
    * @param sibling_pid[IN] the page id of the sibling node.
    * @param siblingKey[OUT] the first key in the sibling node after split.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, PageId sibling_pid, int& siblingKey);

   /**
    * Find the index entry whose key value is larger than or equal to searchKey
    * and output the eid (entry id) whose key value &gt;= searchKey.
    * if the searchKey is larger than any key in all entries,
    * eid will be set to be the largest entry plus one,
    * such that the insertion following the locate function
    * will insert the key at the end of node.
    * Remember that keys inside a B+tree node are sorted.
    * @param searchKey[IN] the key to search for.
    * @param eid[OUT] the entry number that contains a key larger              
    *                 than or equalty to searchKey.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locate(int searchKey, int& eid);

   /**
    * Read the (key, rid) pair from the eid entry.
    * @param eid[IN] the entry number to read the (key, rid) pair from
    * @param key[OUT] the key from the slot
    * @param rid[OUT] the RecordId from the slot
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC readEntry(int eid, int& key, RecordId& rid);

   /**
    * Return the pid of the next slibling node.
    * @return the PageId of the next sibling node 
    */
    PageId getNextNodePtr();


   /**
    * Set the next slibling node PageId.
    * @param pid[IN] the PageId of the next sibling node 
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC setNextNodePtr(PageId pid);


  private:
    /**
     * the starting position to store the page id for the next sibling
     */
    static const int PID_START_POS = 2 * sizeof(int);

    // the size of an entry, which is a (RecordId, key) pair
    static const int ENTRY_SIZE = sizeof(RecordId) + sizeof(int);

    /**
     * the starting block of a page consists of
     * a sizeof(int) block to decide whether this node is a leaf or not,
     * a sizeof(int) block for the number of keys in a node,
     * and a sizeof(PageId) block for the next sibling page id
     */
    static const int START_BLOCK_SIZE = 2*sizeof(int) + sizeof(PageId);

    static const int MAX_ENTRY_PER_NODE = ( PageFile::PAGE_SIZE - START_BLOCK_SIZE ) / ENTRY_SIZE;

    /**
      * insert the (rid, key) pair at the entry with entry id eid
      * @param eid[IN] the entry id at which the (rid, key) pair to be inserted
      * @param key[IN] the key value to be inserted
      * @param rid[IN] the record id value to be inserted
      */
    RC insertAtEntry(int eid, int key, const RecordId& rid);

    /**
     * shift the block of entries one entry uint to the right;
     * used before inserting an new entry.
     * @param startEid[IN] the starting entry needed to be shifted
     * @param entryCount[IN] the number of entries to be shifted
     */
    RC shiftOneEntryRight( int startEid, int entryCount );
}; 


/**
 * BTNonLeafNode: The class representing a B+tree nonleaf node.
 */
class BTNonLeafNode : public BTNode {
  public:
    BTNonLeafNode();

   /**
    * Return true if the node is full,
    * otherwise, return false.
    */
    bool isFull();


   /**
    * Insert a (key, pid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, PageId pid);

   /**
    * Insert the (key, pid) pair to the node
    * and split the node half and half with sibling.
    * The sibling node MUST be empty when this function is called.
    * The middle key after the split is returned in midKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
    * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey);

   /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * Remember that the keys inside a B+tree node are sorted.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locateChildPtr(int searchKey, PageId& pid);

    RC initializeNode();
    
   /**
    * Initialize the root node with (pid1, key, pid2).
    * @param pid1[IN] the first PageId to insert
    * @param key[IN] the key that should be inserted between the two PageIds
    * @param pid2[IN] the PageId to insert behind the key
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC initializeRoot(PageId pid1, int key, PageId pid2);
    PageId getPid(int n){PageId p;memcpy(&p,buffer+PID_START_POS + n*PAIR_SIZE,sizeof(PageId));return p;}

  private:
          static const int PAIR_SIZE = sizeof(PageId) + sizeof(int);
          static const int PID_START_POS = 2 * sizeof(int);
          static const int FIRST_KEY_POS = PID_START_POS + sizeof(PageId);
          static const int MAX_KEY = ( PageFile::PAGE_SIZE - PID_START_POS - sizeof(PageId)) / PAIR_SIZE;
          void setKey(int n, int key){memcpy(buffer+PID_START_POS+n*PAIR_SIZE+sizeof(PageId),&key,sizeof(int));}
          void setPid(int n, PageId pid){memcpy(buffer+PID_START_POS+n*PAIR_SIZE,&pid,sizeof(PageId));}
          int getKey(int n){int k;memcpy(&k,buffer+PID_START_POS + n*PAIR_SIZE + sizeof(PageId),sizeof(int));return k;}
//          PageId getPid(int n){PageId p;memcpy(&p,buffer+PID_START_POS + n*PAIR_SIZE,sizeof(PageId));return p;}
//	  int posKey(int n) { return PID_START_POS + n*PAIR_SIZE + sizeof(PageId);}
//	  int posPid(int n) { return PID_START_POS + n*PAIR_SIZE;}
};


#endif /* BTNODE_H */
